/*
 * q1443.java
 * Copyright (C) 2018 crane <crane@crane-pc>
 *
 * Distributed under terms of the MIT license.
 */

// https://www.jiuzhang.com/solution/longest-ab-substring


/**
 *   本参考程序来自九章算法，由 @华助教 提供。版权所有，转发请注明出处。
 * - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
 * - 现有的面试培训课程包括：九章算法班，系统设计班，算法强化班，Java入门与基础算法班，Android 项目实战班，
 * - Big Data 项目实战班，算法面试高频题班, 动态规划专题班
 * - 更多详情请见官方网站：http://www.jiuzhang.com/?source=code
 */

// 题解
// 遍历一遍字符串，用 数组 A 和数组 B 分别保存a的数量减去b的数量 为 i的最长前缀子串的长度和最短前缀子串的长度
// 然后对于枚举每个i，更新答案即可。复杂度O(n)O(n)。


class Solution {
    /**
     * @param s: a String consists of a and b
     * @return: the longest of the longest string that meets the condition
     */
    public int getAns(String s)
    {
        // write your code here
        int len = s.length();
        int dp[] = new int[len + 1];
        dp[1] = (s.charAt(0) - 'A') == 1 ? 1 : -1;

        // a-b个数之差: cnt_a - cnt_b
        for (int i = 2; i <= len; i++)
        {
            dp[i] = (s.charAt(i - 1) - 'A') == 1 ? 1 : -1;
            dp[i] += dp[i - 1];
        }

        int max = 0, begin;
        Map<Integer, Integer> m = new HashMap<>();      // {span : index}

        for (int i = 1; i <= len; i++)
        {
            begin = m.getOrDefault(dp[i], 0);
            if (begin == 0 && dp[i] != 0)
            {
                m.put(dp[i], i);
            }
            else
            {
                if (i - begin > max) {
                    max = i - begin;
                }
            }
        }
        return max;
    }
}
